package 链表;

import java.util.HashMap;
import java.util.Map;

public class 剑指No35复杂链表的复制 {

    /**
     * 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，
     * 每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
     *
     *  
     *
     * 示例 1：
     * 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
     * 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
     * 示例 2：
     * 输入：head = [[1,1],[2,1]]
     * 输出：[[1,1],[2,1]]
     *
     * 简单来说就是深拷贝一个链表
     */

    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    /**
     * 生成一个节点后,用Map给原节点和现节点来个映射关系
     */
    public static Node copyRandomList(Node head) {

        if(head==null)
            return null;

        /**
         * Map<原Node,拷贝Node>
         * 怎么去遍历呢?
         * 1.原节点是否可以在Map中存在?
         * 1.4存在就直接取出拷贝的Node,然后拼接即可
         * 1.8不存在,就拷贝Node,然后存入Map,再拼接
         *
         * 2.查看Random是否存在节点当中
         * 2.4存在,就拼接好拷贝Node
         * 2.8不存在,就拷贝Node,然后存入Map,在拼接
         *
         */

        Map<Node,Node> map=new HashMap<>();
        Node headNode=new Node(head.val);
        Node myNode=headNode;
        map.put(head,myNode);

        Node cur=head;

        while (cur!=null){

            Node next=cur.next;//原

            //之前是否已经创建了Node
            Node myNextNode = map.get(next);

            if(myNextNode!=null){
                myNode.next=myNextNode;
            }else{
                if(next!=null) {
                    Node node = new Node(next.val);
                    map.put(next, node);//放入
                    myNode.next = node;//再拼接
                }
            }

            Node ran=cur.random;//原

            Node myRan=map.get(ran);

            if(myRan!=null){
                myNode.random=myRan;
            }else{
                if(ran!=null) {
                    Node node = new Node(ran.val);
                    map.put(ran, node);//放入
                    myNode.random = node;//再拼接
                }
            }

            myNode=myNode.next;
            cur=cur.next;

        }

        return headNode;

    }

    public static void main(String[] args) {

        //[[7,null],[13,0],[11,4],[10,2],[1,0]]
        Node node=new Node(7);
        node.random=null;

        Node node1=new Node(13);
        node.next=node1;
        node1.random=node;

        Node node2=new Node(11);
        node1.next=node2;

        Node node3=new Node(10);
        node2.next=node3;
        node3.random=node2;

        Node node4=new Node(1);
        node3.next=node4;
        node2.random=node4;
        node4.random=node;

        Node node5 = copyRandomList(node);
        System.out.println(node5);

    }

}
